from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # 排序是为了方便使用双指针法，并且能跳过重复元素
        ans = []
        n = len(nums)
        for i in range(n - 2): # 遍历到 n-2 是因为需要三个数，后面至少留两个位置给 j 和 k。
            x = nums[i]
            if i > 0 and x == nums[i - 1]:  # 如果当前数字和前一个相同，则跳过，避免重复
                continue
            if x + nums[i + 1] + nums[i + 2] > 0:  # 当前 x 加上后面两个最小的数已经大于 0，由于数组是升序，后面的数更大
                break
            if x + nums[-2] + nums[-1] < 0:  # 当前 x 加上最大的两个数仍然小于 0，说明 x 太小，需要增大 x
                continue

            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k] # 根据三数之和 s 与 0 的大小关系移动指针：
                if s > 0:
                    k -= 1 # s > 0：说明总和太大，k 左移减小总和。
                elif s < 0:
                    j += 1 # j 右移增大总和。
                else:  # 三数之和为 0
                    ans.append([x, nums[j], nums[k]])
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:  # 跳过重复数字
                        j += 1
                    k -= 1 # 必须同时移动两个指针，才能有可能找到新的和为 0 的组合。
                    while k > j and nums[k] == nums[k + 1]:  # 跳过重复数字
                        k -= 1
        return ans